package leetcode_700;

/**
 *@author 周杨
 *Keys2Keyboard_650 粘贴板问题 每次只能全量复制和粘贴 问最小几步能达到目标字符串
 *describe:用动态规划 每次记录当前最小步数 当整数时直接赋值 AC 51%
 *2018年9月26日 下午2:15:13
 */
public class Keys2Keyboard_650 {
	 public int minSteps(int n) {
	        int[] dp = new int[n+1];

	        for (int i = 2; i <= n; i++) {
	            dp[i] = i;
	            for (int j = i-1; j > 1; j--) {//回头找 有没有能整除的 
	                if (i % j == 0) {
	                    dp[i] = dp[j] + (i/j);
	                    break;
	                }
	                
	            }
	        }
	        return dp[n];
	    }
}
